查看原文
其他

生产计划:运筹学线性规划与SAP Optimizer

Edison Edison的SAP实践与修行 2023-04-15
线性规划:LP与MILP

众所周知,生产计划问题或者排产问题,其实是一个诸多约束条件的最优或次优解的求解过程。比如在制造工厂中的生产排产MPS中最常遇到的便是既要考虑产成品生产工艺上的产能制约,同时还要考虑其下层BOM中物料的供应制约,所以这二者是一个非常灵活的组合制约因子,比如 T+X 天可能产能足够、但T+X天的物料却无法全部供应到位,所以T+X无法排该笔生产计划;但如果把这一笔计划推迟到当其所需要用到的物料能供应到位的T+Y天,却又很有可能此时T+Y天的产能无法满足,即依然无法排该笔生产计划。

如果在这个限制条件场景中再加入更多的主产品,更多的组件物料,比如主生产过程用到AB物料,A物料可以在T+Y供应到位,而B物料却只能在T+Z天供应到位,则整个生产排产过程就变得更加复杂。

再进一步,如果这个生产排产过程处于一个供应网络的场景中,例如A工厂的需求可以由B工厂的库存或生产排产来满足,还可以由C工厂来满足,但ABC不同工厂间的需求满足路线不同,供给运输方式不同,运输产能不同,运输成本不同,各工厂的库容、仓储成本不同,那么通过生产排产的过程将变得更加难以快速实现。

诸上所述,生产计划,是一个非常古老但却是非常普遍的社会应用场景,也是从很早开始便是运筹学的一个经典应用场景。

当多个约束条件或者制约因子共同作用,不同约束条件的组合方式形成不同的解决方案,而不同的解决方案带来不同的应用效果(目标)。其中这些制约因子,与最终的效果(目标),在其他因子保持不变的假设下,呈现出一种线性的变化例如有规律的递增或递减,例如生产成本这一个制约因子,生成一件比如是100元,那生成10件为1000元或有规律的结果(比如90元,抑或110元),这便是我们常说的“线性规划”。在计算机语言上,线性规划,即Linear ProgrammingLP)是解决此类问题的首选方案。

但是在现实应用过程中,除了这些线性的制约因子外,还有一些制约因子表现的很特别,例如最常见的批量大小Lot-size,如果按照纯粹的线性规划,在不同的制约因子组合下得到的解决方案,很有可能导致建议的供给(例如排产订单)的大小满足了线性规划的结果,比如呈现为小数,但实际应用过程中,订单大小却不能是小数必须是整数,这种场景很普遍,在以整数为大小管理的行业尤其如此,比如装备制造、汽车、光伏等等。所以在计算机语言上,在连续型的LP的基础之上,再结合离散型的整数约束,发展出了整数的线性规划Mixed Integer Linear ProgrammingMILP)。

值得说明的是,LPMILP只是此类问题的2 种常用算法而已,除此之外,还有其他的解决方案,比如与线性规划相对应的非线性规划NLPNon Linear Programming)、遗传算法(Generic Algorism)等等,限于本人能力有限,更待深入研究。

单论本篇所关注的LPMILP,对于线性规划,从实现方法来看,最简单的理解可以为,首先需要依据实际需要设定“目标函数”(即最后不同的解决方案所要达到的“效果”),然后各个制约因子是变量,所有的变量再乘上各自可能的数量,以目标函数为目标,在可行域中求得最优解或者次优解,此便是算法最终的解决方案。

在整个过程中,可以看出,相比纯粹的LP,从算法以及计算机实现上而言,MILP的复杂度将会更高。举一个简单的例子,比如在LP的过程中,所有的制约因子考虑后,订单大小为1.5 pc可以达到效果(比如成本目标)最优,但结合整数后,即此时必须是2 pc,但如果这个制约因子变成了2pc后,可能又从整体上对目标函数造成不再是“最优”,即可以通过调整其他制约因子的数量来得到更优的结果,但如果调整其他因子后又可能导致更其他因子不再是最优,循环反复,MILP将带来比LP成倍的复杂性。



SAP产品:Optimizer

优化器Optimizer,是SAP APS软件即APO提供的一种计划场景的解决方案,目前的产品除了S4HANA中刚推出的PPO,主要有SNP OptimizerPPDS Optimizer。虽然这些产品的核心算法引擎都是外部的算法工具,譬如SNP Optimizer使用的CPLEXPPDS Optimizer使用的APEX等,但是SAP与这些算法引擎通过深度的嵌入结合来满足真实的业务需求。

其中PPDS Optimizer主要应用于排产结果的再次优化(所以几乎不使用其来创建计划结果),它提供了诸如供结时间长度、设置时间、设置成本、制造模式成本、总延迟成本、最大延迟成本等6大制约因子,但是它采用的算法不是前面提到的线性规划LP/MILP,而是遗传算法(Generic Algorism),即在设定时间内使用不同的子孙代际的不断迭代来求得相对最优的解决方案。PPDS Optimizer在先前的一些排产实操记录中已有实际应用案例的说明(例如,“换模切换”的SAP排产解决方案),在此便不再赘述。

SNP Optimizer则是前面提到的线性规划的实际应用,它的主要应用就是在整体供应链中考虑各个制约因子通过线性规划来创建得到本次计划的排产结果,主要可以考虑的制约因子便有:

·         生产制造成本

·         生产资源的产能及成本

·         采购成本

·         库存仓储成本

·         处理资源的产能及成本

·         产品生命周期成本

·         安全库存未满足成本

·         运输成本

·         运输资源产能与成本

·         延期交货成本

·         不交货成本

如果上述各制约因子分别是变量x, y, z,….,则SNP Optimizer的目标函数就可以依据实际业务所需设置为 MaxProfit)或MinCost  = x * v1 + y * v2 + z * v3 + ….,最终通过算法引擎对各变更的线性规划的复杂演算得到最优的解决方案,例如v1 = 100, v2 = 200, v3 = 300…等。

从技术上而言,在整个计划过程中,SAP与引擎算法结合,其过程可以简单地理解为以下过程:

SNP Optimizer的确很强大,但是限于当初产品推出时的考虑,目前SNP Optimizer还是具有很多的应用限制,例如其只能支持MTS的应用场景,不支持VC配置场景,不支持多产线共线混排等等。

但通过上面的整个运算过程中,我们可以看到SAP其实主要是负责抽取数据、准备外部引擎所需要的数据,并最终接收引擎排出的结果数据。所以,在进入引擎前以及出引擎后,在SAP端就有大量的可能来对本身标准的数据进行干预,例如SAP中国团队就可以通过异常灵活的数据改造让SNP Optimizer支持诸如以下原本并不支持的业务场景,以满足实际业务所需:


结语

生产计划这一复杂的实际业务应用,其背后的算法本质其实是相当复杂,但在实际生活中,限于行业的特性以及APS产品的限制,很多时候我们通过软件做的并不是在做完整的“生产计划”或者是非常简单的初级计划,例如在汽车行业,我们的排产更多的是一种“排序”的应用,而真正在排产过程中也很少或者很难去关注到除产能外比如物料齐套、仓储成本等制约因素。

而应用像SNP Optimizer这样的线性规划的工具,不光是像PPDS那样的产能排产、调序工具,相信可以更加有效地从“计划本身”来真正地辅助排产过程。



相关延伸


  1. APS高级排产的思考

  2. 汽车行业-颜色件物料 解决方案小结

  3. 卡车行业的ERP方案随笔 - 相较乘用车

  4. 深入IS Auto五日谈 1:关于Auto、关于IS Auto

  5. 多产线或共线排产的SAP解决方案

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存